백준 2357번

오늘 풀어본 문제는 백준의 2357번 문제¹이다. 문제 풀이에 사용한 언어는 C++ 이다.

solved.ac 기준 CLASS

CLASS 6

문제 정보

이 문제의 내용과 조건은 다음과 같다.

문제

$N$ $(1 \le N \le 100,000)$ 개의 정수들이 있을 때, $a$ 번째 정수부터 $b$ 번째 정수까지 중에서 제일 작은 정수, 또는 제일 큰 정수를 찾는 것은 어려운 일이 아니다. 하지만 이와 같은 $a$, $b$ 의 쌍이 $M$ $(1 \le M \le 100,000)$ 개 주어졌을 때는 어려운 문제가 된다. 이 문제를 해결해 보자.

여기서 $a$ 번째라는 것은 입력되는 순서로 $a$ 번째라는 이야기이다. 예를 들어 $a=1$, $b=3$ 이라면 입력된 순서대로 $1$ 번, $2$ 번, $3$ 번 정수 중에서 최소, 최댓값을 찾아야 한다. 각각의 정수들은 $1$ 이상 $1,000,000,000$ 이하의 값을 갖는다.

입력

첫째 줄에 $N$, $M$ 이 주어진다. 다음 $N$ 개의 줄에는 $N$ 개의 정수가 주어진다. 다음 $M$ 개의 줄에는 $a$, $b$ 의 쌍이 주어진다.

출력

$M$ 개의 줄에 입력받은 순서대로 각 $a$, $b$ 에 대한 답을 최솟값, 최댓값 순서로 출력한다.

풀이과정

1번째 시도

문제를 보고 세그먼트 트리를 활용하여 해결할 수 있다는 걸 알 수 있었다. 해결하기 위해 사용한 방식은 다음과 같다.

기존에 만들어 둔 세그먼트 트리 자료 구조를 트리를 처음 구성하는 함수와 쿼리 함수가 최솟값과 최댓값의 std::pair 를 다루도록 개조하였다.
입력에 맞게 쿼리를 보내고 결과를 출력하도록 main 함수를 작성하였다.

코드는 다음과 같이 작성하였다. 제출할 때는 헤더파일의 코드를 붙여넣어 제출하였다.

segment_tree.hpp

#ifndef __SEGMENT_TREE_HPP__
#define __SEGMENT_TREE_HPP__

#include <vector>

using ull = unsigned long long int;

class SegmentTree {
private:
    std::vector<std::pair<ull, ull>> tree;
    std::vector<ull> arr;
    size_t n;

    void build(size_t idx, size_t left, size_t right) {
        if (left == right) {
            tree[idx].first = arr[left];
            tree[idx].second = arr[left];
            return;
        }

        size_t mid = (left + right) / 2;

        build(2 * idx, left, mid);
        build(2 * idx + 1, mid + 1, right);

        const std::pair<ull, ull>& leftValue = tree[2 * idx];
        const std::pair<ull, ull>& rightValue = tree[2 * idx + 1];

        tree[idx].first = std::min(leftValue.first, rightValue.first);
        tree[idx].second = std::max(leftValue.second, rightValue.second);
    }

    const std::pair<ull, ull> query(size_t i, size_t j, size_t node, size_t currentLeft, size_t currentRight) {
        if (j < currentLeft || currentRight < i) {
            return std::make_pair(ULLONG_MAX, 0ULL);
        }
        else if (i <= currentLeft && currentRight <= j) {
            return tree[node];
        }
        else {
            size_t mid = (currentLeft + currentRight) / 2;
            const std::pair<ull, ull> leftValue = query(i, j, 2 * node, currentLeft, mid);
            const std::pair<ull, ull> rightValue = query(i, j, 2 * node + 1, mid + 1, currentRight);

            ull minimum = std::min(leftValue.first, rightValue.first);
            ull maximum = std::max(leftValue.second, rightValue.second);
            
            return std::make_pair(minimum, maximum);
        }
    }

public:
    SegmentTree(const std::vector<ull>& a) : arr(a), n(a.size()) {
        tree.resize(4 * n + 1);
        build(1, 0, n - 1);
    }

    const std::pair<ull, ull> query(size_t i, size_t j) {
        return query(i, j, 1, 0, n - 1);
    }
};

#endif // !__SEGMENT_TREE_HPP__

main.cpp

#include <bits/extc++.h>
#include "segment_tree.hpp"

using namespace __gnu_pbds;
using namespace std;

using ll = long long int;
using ull = unsigned long long int;

using pll = pair<ll, ll>;

int main(void) {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);

    int N, M;
    cin >> N >> M;

    vector<ull> A(N);
    for (int i=0; i<N; i++) {
        cin >> A[i];
    }

    SegmentTree tree(A);

    for (int i=0; i<M; i++) {
        int a, b;
        cin >> a >> b;

        a--;
        b--;
        
        pll answer = tree.query(a, b);
        cout << answer.first << ' ' << answer.second << '\n';
    }
    
    return 0;
}

그러자 모든 테스트 케이스를 통과하고 ‘맞았습니다’가 나오는 것을 확인할 수 있었다.

마무리

역시 한 번 세그먼트 트리를 만들어 두니 두고두고 써먹는 것 같다. 요구하는 쿼리가 달라지긴 해도 방식의 본질이 변하지 않기 때문에 계속 써먹을 수 있는 것 같다!

그러나 CLASS 7 에서는 더 이상 내가 만든 것 만으로는 안되고 Lazy Propagation Segment Tree 라는 걸 만들어야 한다는데, 전역 전까지 할 수 있을지 조금 걱정되기 시작했다… 지금은 우선 CLASS 6 문제들을 해결하는 것에 집중해야겠다.

내가 만든 세그먼트 트리 자료구조는 내 레포지토리²에서 확인할 수 있다. 문제에 맞게 개조한 버전은 여기³서 확인할 수 있다. 필요한 사람은 참고하길 바란다.

오늘의 PS는 여기까지!

1: https://www.acmicpc.net/problem/2357
2: https://github.com/ChoiCube84/baekjoon-solutions/blob/main/C%2B%2B/custom_data_structures/segment_tree.hpp
3: https://github.com/ChoiCube84/baekjoon-solutions/blob/main/C%2B%2B/2357/segment_tree.hpp

← Previous Post Next Post →